package come.lanqiao.kruskal;

import java.util.Arrays;

public class KruskalCase {
	private int edgeNum;//边的个数
	private char[] vertexs;//顶点数组
	private int[][] matrix;//邻接矩阵
	//使用INF表示两个顶点之间不能连同
	private static final int INF = Integer.MAX_VALUE;

	public static void main(String[] args) {
		char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//克鲁斯卡尔算法的邻接矩阵
		int matrix[][] = {
		/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ 	{  0,  12,  INF, INF, INF, 16,  14},
/*B*/ 	{  12,  0,   10, INF, INF,  7, INF},
/*C*/ 	{ INF, 10,   0,   3,   5,  6, INF},
/*D*/ 	{ INF,INF,   3,   0,   4,INF, INF},
/*E*/ 	{ INF,INF,   5,   4,   0,  2,   8},
/*F*/ 	{  16,  7,   6, INF,   2,  0,   9},
/*G*/   {  14,INF, INF, INF,   8,  9,   0}};
		//创建KruskalCase对象实例
		KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
		//输出构建的
		kruskalCase.print();
		System.out.println("=====");
		EData[] edges = kruskalCase.getEdges();
		System.out.println(Arrays.toString(edges));
		kruskalCase.sortEdges(edges);
		System.out.println(Arrays.toString(edges));
		System.out.println("======");
		kruskalCase.kruskal();
	}
	
	//构造器
	public KruskalCase(char[] vertexs, int[][] matrix) {
		//初始化顶点数组和边的个数
		int vlen = vertexs.length;
		//初始化顶点,复制拷贝的方式(不影响外面的数组)
		this.vertexs = new char[vlen];
		for (int i = 0; i < vertexs.length; ++i) {
			this.vertexs[i] = vertexs[i];
		}
		//直接赋值
		//this.vertexs = vertexs;
		//初始化边
		this.matrix = new int[vlen][vlen];
		//同理
		for (int i = 0; i < vlen; ++i) {
			for (int j = 0; j < vlen; ++j) {
				this.matrix[i][j] = matrix[i][j];
			}
		}
		//统计有效边
		for (int i = 0;i < vlen; ++i) {
			for (int j = i + 1; j < vlen; ++j) {
				if (this.matrix[i][j] != INF) {
					++edgeNum;
				}
			}
		}
	}
	
	public void kruskal() {
		int index = 0;//表示最后结果数组的索引
		int[] ends = new int[edgeNum];//用于保存“已有的最小生成树”中的每个顶点在最小生成树的终点
		//创建结果数组。保存最后的最小生成树
		EData[] rets = new EData[edgeNum];
		//获取图中的所有边的集合
		EData[] edges = getEdges();
		//按照边的权值大小进行排序（从小到大）
		sortEdges(edges);
		//遍历edges数组，将边添加到最小生成树中时，判断准备加入的边是否形成了回路
		for (int i = 0; i < edgeNum; ++i) {
			//获取第i条边的第一个顶点
			int p1 = getPosition(edges[i].start);
			//获取第i条边的第二个顶点
			int p2 = getPosition(edges[i].end);
			//获取p1这个顶点在已有最小生成树中的终点
			int m = getEnd(ends, p1);
			//获取p2这个顶点在已有最小生成树中的终点
			int n = getEnd(ends, p2);
			//是否构成回路
			if (m != n) {//没有回路
				ends[m] = n;//设置m在“已有最小生成树”中的终点（类似并查集）
				rets[index++] = edges[i];//将该条边加入到rets数组
			}
		}
		//统计打印最小生成树
		for (int i = 0; i < index; ++i) {
			System.out.println(rets[i]);
		}
	}
	
	
	
	
	//打印邻接矩阵
	public void print() {
		System.out.println("邻接矩阵：");
		for (int[] i : matrix) {
			System.out.println(Arrays.toString(i));
		}
	}
	
	//对边进行排序处理，冒泡排序
	/**
	 * 功能：对边进行排序处理，冒泡排序
	 * @param edges 边的集合
	 */
	private void sortEdges(EData[] edges) {
		for (int i = 0; i < edges.length - 1; ++i) {
			for (int j = 0; j < edges.length - 1 - i; ++j) {
				if (edges[j].weight > edges[j + 1].weight) {//交换
					EData temp = edges[j];
					edges[j] = edges[j + 1];
					edges[j + 1] = temp;
				}
			}
		}
	}
	
	/**
	 * 
	 * @param ch 顶点的值，比如：'A', 'B'
	 * @return 返回ch顶点对应的下标，如果找不到，返回-1
	 */
	private int getPosition(char ch) {
		for (int i = 0; i < vertexs.length; ++i) {
			if (vertexs[i] == ch) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 功能：获取图中的边，放到EData[]数组，后面需要遍历
	 * 是通过matrix邻接矩阵来获取
	 * EDdata[] 形式[['A', 'B', '12'], ['B', 'F', 7],......]
	 * @return 
	 */
	private EData[] getEdges() {
		int index = 0;
		EData[] edges = new EData[edgeNum];
		for (int i = 0; i < vertexs.length; ++i) {
			for (int j = i + 1; j < vertexs.length; ++j) {
				if (matrix[i][j] != INF) {
					edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
				}
			}
		}
		return edges;
	}
	
	/**
	 * 功能：获取下标为i的顶点的终点，用于后面判断两个顶点的终点是否相同
	 * @param ends 数组记录了各个顶点对应的是哪个，ends数组在遍历过程逐渐形成
	 * @param i 表示传入的顶点对应的下标
	 * @return 返回的是下标为i的这个顶点对应的终点的下标
	 */
	//思路类似并查集
	private int getEnd(int[] ends, int i) {
		while (ends[i] != 0) {
			i = ends[i];
		}
		return i;
	}
}

//创建一个类EData，它的对象实例就表示一条边
class EData {
	char start;//边的一个点
	char end;//边的另外一个点
	int weight;//边的权值
	
	//构造器
	public EData(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	//重写toString
	@Override
	public String toString() {
		return "EData [<" + start + ", " + end + ">= " + weight + "]";
	}
	
}
